package com.datastructure3.backtrack;

import org.junit.Test;

import javax.xml.bind.SchemaOutputResolver;
import java.security.cert.PKIXParameters;
import java.util.*;

/**
 * @author: 临晖
 * @since: 2024-08-08
 */
public class Solution {


    /**
     * 77. 组合
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
     * 你可以按 任何顺序 返回答案。
     *
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        combine_(n, k, 1, path, res);
        return res;
    }

    public void combine_(int n, int k, int start, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i <= n; i++) {

            if (i - k + 1 <= 0) {
                return;
            }

            path.add(i);
            combine_(n, k, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }


    /**
     * 216. 组合总和 III
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
     * 只使用数字1到9
     * 每个数字 最多使用一次
     * 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
     *
     * @param k
     * @param n
     * @return
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        int sum = 0;
        combinationSum3_(k, n, 1, sum, path, res);
        return res;
    }


    public void combinationSum3_(int k, int n, int start, int sum, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == k) {
            if (sum == n) {
                res.add(new ArrayList<>(path));
            }
            return;
        }


        for (int i = start; i <= 9; i++) {

            //sum += i;
            path.add(i);

            combinationSum3_(k, n, i + 1, sum + i, path, res);

            //sum -= i;
            path.remove(path.size() - 1);
        }
    }


    /**
     * 17. 电话号码的字母组合
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     *
     * @param digits
     * @return
     */
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if ("".equals(digits)) {
            return res;
        }

        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        StringBuilder path = new StringBuilder();

        letterCombinations_(digits, 0, path, res, map);
        return res;

    }


    public void letterCombinations_(String digits, int start, StringBuilder path, List<String> res, Map<Character, String> map) {
        if (path.length() == digits.length()) {
            res.add(path.toString());
            return;
        }


        String str = map.get(digits.charAt(start));
        for (int i = 0; i < str.length(); i++) {
            path.append(str.charAt(i));

            letterCombinations_(digits, start + 1, path, res, map);

            path.delete(path.length() - 1, path.length());
        }
    }


    /**
     * 39. 组合总和
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
     * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
     * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
     * <p>
     * candidates = [2,3,6,7], target = 7
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        combinationSum_(candidates, target, 0, 0, path, res);
        return res;
    }

    public void combinationSum_(int[] candidates, int target, int start, int sum, List<Integer> path, List<List<Integer>> res) {

        if (sum > target) {
            return;
        }

        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++) {

            if (sum + candidates[i] > target) {
                return;
            }

            path.add(candidates[i]);

            combinationSum_(candidates, target, i, sum + candidates[i], path, res);

            path.remove(path.size() - 1);
        }
    }


    /**
     * 40. 组合总和 II
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     * candidates 中的每个数字在每个组合中只能使用 一次 。
     * 注意：解集不能包含重复的组合。
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        combinationSum2_(res, path, target, 0, candidates, 0);
        return res;
    }

    public void combinationSum2_(List<List<Integer>> res, List<Integer> path, int target, int sum, int[] candidates, int start) {
        if (sum > target) {
            return;
        }

        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            sum += candidates[i];

            if (sum > target) {
                return;
            }

            path.add(candidates[i]);
            combinationSum2_(res, path, target, sum, candidates, start);
            path.remove(path.size() - 1);

            sum -= candidates[i];
        }

    }


    /**
     * 131. 分割回文串
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
     * 回文串
     * 。返回 s 所有可能的分割方案。
     *
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {

        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        partition_(s, 0, res, path);

        return res;
    }

    public void partition_(String str, int start, List<List<String>> res, List<String> path) {

        if (start >= str.length()) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < str.length(); i++) {
            String subText = str.substring(start, i + 1);

            if (isPalindrome(subText)) {
                path.add(subText);

                partition_(str, i + 1, res, path);

                path.remove(path.size() - 1);

            }

        }
    }

    public boolean isPalindrome(String subText) {
        int start = 0;
        int last = subText.length() - 1;

        while (start <= last) {
            if (subText.charAt(start) != subText.charAt(last)) {
                return false;
            }

            start++;
            last--;
        }

        return true;
    }


    /**
     * 78. 子集
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
     * 子集
     * （幂集）。
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        res.add(new ArrayList<>(path));
        subsets_(nums, 0, res, path);
        return res;
    }

    public void subsets_(int[] nums, int start, List<List<Integer>> res, List<Integer> path) {

        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            res.add(new ArrayList<>(path));

            subsets_(nums, i + 1, res, path);

            path.remove(path.size() - 1);
        }

    }


    /**
     * 90. 子集 II
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的
     * 子集
     * （幂集）。
     * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        res.add(new ArrayList<>(path));
        subsetsWithDup_(nums, 0, res, path);
        return res;
    }

    public void subsetsWithDup_(int[] nums, int start, List<List<Integer>> res, List<Integer> path) {

        for (int i = start; i < nums.length; i++) {

            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }

            path.add(nums[i]);
            res.add(new ArrayList<>(path));

            subsets_(nums, i + 1, res, path);

            path.remove(path.size() - 1);
        }

    }

    /**
     * 491. 非递减子序列
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
     * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
     * <p>
     * 对于通过排序得到的序列，只需要
     * //if (i > start && nums[i] == nums[i - 1]) {
     * //    continue;
     * //}
     * 就好，但是，对于不可排序的序列，如何去重呢？
     * HashMap<Integer, Boolean> map = new HashMap<>();
     * for (int i = start; i < nums.length; i++) {
     * Boolean flag = map.getOrDefault(nums[i], false);
     * if (!flag) {
     * <p>
     * }
     * }
     * 因为未排序的序列，相同的数字可能是不挨着的，所以，我们通过第一种方式无法判断，这时候，创建一个map序列，要来标记某个数字
     * 是否被遍历过，以此来达到去重的目的
     *
     * @param nums
     * @return
     */
    //todo 新的剪枝算法
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        findSubsequences_(nums, 0, res, path);

        return res;
    }


    public void findSubsequences_(int[] nums, int start, List<List<Integer>> res, List<Integer> path) {

        HashMap<Integer, Boolean> map = new HashMap<>();
        for (int i = start; i < nums.length; i++) {
            Boolean flag = map.getOrDefault(nums[i], false);
            //if (i > start && nums[i] == nums[i - 1]) {
            //    continue;
            //}

            if (!flag) {
                map.put(nums[i], true);
                int len = path.size();
                if (len == 0) {
                    path.add(nums[i]);
                } else if (len > 0 && nums[i] >= path.get(len - 1)) {
                    path.add(nums[i]);
                    res.add(new ArrayList<>(path));
                } else {
                    continue;
                }

                findSubsequences_(nums, i + 1, res, path);
                path.remove(path.size() - 1);
            }

        }

    }


    /**
     * 46. 全排列
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        permute_(res, path, nums, new boolean[nums.length]);

        return res;
    }

    public void permute_(List<List<Integer>> res, List<Integer> path, int[] nums, boolean[] isInterview) {

        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!isInterview[i]) {
                path.add(nums[i]);
                isInterview[i] = true;

                permute_(res, path, nums, isInterview);

                path.remove(path.size() - 1);
                isInterview[i] = false;
            }
        }


    }


    /**
     * 47. 全排列 II
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
     * <p>
     * todo 值得借鉴
     * 是重新创建一个新的数组，用于标记已使用过的数字，还是将已使用的数字变成一个不存在的数字，来以此标记已经使用过，视情况而定
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique(int[] nums) {

        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        permuteUnique_(res, path, nums);
        return res;

    }


    public void permuteUnique_(List<List<Integer>> res, List<Integer> path, int[] nums) {

        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }


        for (int i = 0; i < nums.length; i++) {
            int temp = nums[i];

            if (nums[i] == -11 || (i > 0 && nums[i] == nums[i - 1])) {
                continue;
            }
            path.add(nums[i]);
            nums[i] = -11;
            permuteUnique_(res, path, nums);
            path.remove(path.size() - 1);
            nums[i] = temp;
        }

    }


    /**
     * 332. 重新安排行程
     * 已解答
     * 困难
     * 相关标签
     * 相关企业
     * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
     * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
     * 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
     * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
     *
     * @param tickets
     * @return
     */
    public List<String> findItinerary(List<List<String>> tickets) {
        List<String> res = new ArrayList<>();
        Map<String, Map<String, Integer>> map = new HashMap<>();
        int count = tickets.size() + 1;

        //for (List<String> ticket : tickets) {
        //    Map<String, Integer> temp;
        //    if (map.containsKey(ticket.get(0))) {
        //        temp = map.get(ticket.get(0));
        //        temp.put(ticket.get(1), temp.getOrDefault(ticket.get(1), 0) + 1);
        //    } else {
        //        temp = new TreeMap<>();
        //        temp.put(ticket.get(1), 1);
        //    }
        //    map.put(ticket.get(0), temp);
        //}

        for (List<String> ticket : tickets) {
            Map<String, Integer> temp;
            if (map.containsKey(ticket.get(0))) {
                temp = map.get(ticket.get(0));
                temp.put(ticket.get(1), temp.getOrDefault(ticket.get(1), 0) + 1);
            } else {
                temp = new TreeMap<>();
                temp.put(ticket.get(1), 1);

            }
            map.put(ticket.get(0), temp);
        }

        res.add("JFK");
        findItinerary_(res, map, count);
        return res;
    }


    public boolean findItinerary_(List<String> res, Map<String, Map<String, Integer>> map, int count) {

        if (res.size() == count) {
            return true;
        }

        String str = res.get(res.size() - 1);
        if (map.containsKey(str)) {
            Map<String, Integer> map1 = map.get(str);
            for (Map.Entry<String, Integer> entry : map1.entrySet()) {
                String key = entry.getKey();
                Integer value = entry.getValue();

                //添加

                if (value > 0) {
                    res.add(key);
                    entry.setValue(value - 1);

                    if (findItinerary_(res, map, count)) {
                        return true;
                    }

                    res.remove(res.size() - 1);
                    entry.setValue(value);
                }


            }
        }

        return false;

    }


    /**
     * 51. N 皇后
     * 已解答
     * 困难
     * 相关标签
     * 相关企业
     * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
     * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
     * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
     * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
     *
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        List<List<String>> res = new ArrayList<>();
        solveNQueens_(queens, 0, res);

        return res;
    }


    public void solveNQueens_(int[] queens, int start, List<List<String>> res) {

        if (start == queens.length) {
            List<String> temp = convertToString(queens);
            res.add(temp);
            return;
        }


        for (int i = 0; i < queens.length; i++) {
            if (isLine(start, i, queens)) {
                queens[start] = i;
                solveNQueens_(queens, start + 1, res);
            }
        }
    }

    public List<String> convertToString(int[] queens) {
        List<String> temp = new ArrayList<>();
        for (int i = 0; i < queens.length; i++) {
            StringBuilder str = new StringBuilder("");

            for (int j = 0; j < queens.length; j++) {

                if (j == queens[i]) {
                    str.append("Q");
                } else {
                    str.append(".");
                }
            }

            temp.add(str.toString());
        }

        return temp;
    }

    //判断是不是在同一条直线上
    public boolean isLine(int x, int y, int[] queens) {
        for (int i = 0; i < x; i++) {
            //判断是否为同一列
            if (queens[i] == y) {
                return false;
            }
            //判断是否在同一斜线上

            if (Math.abs(x - i) == Math.abs(y - queens[i])) {
                return false;
            }
        }

        return true;
    }


    /**
     * 37. 解数独
     * 已解答
     * 困难
     * 相关标签
     * 相关企业
     * 编写一个程序，通过填充空格来解决数独问题。
     * 数独的解法需 遵循如下规则：
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
     * 数独部分空格内已填入了数字，空白格用 '.' 表示。
     *
     * @param board
     */
    public void solveSudoku(char[][] board) {
        solveSudoku_(board, 0, 0);
        System.out.println();
    }


    public boolean solveSudoku_(char[][] board, int x, int y) {


        if (y >= board[0].length) {
            y = 0;
            x++;
        }

        if (x >= board.length) {
            return true;
        }

        if (board[x][y] >= '0' && board[x][y] <= '9') {
            if (solveSudoku_(board, x, y + 1)){
                return true;
            }
        } else {
            for (int z = '1'; z <= '9'; z++) {

                if (isTogether(x, y, (char) z, board)) {
                    board[x][y] = (char) z;
                    if (solveSudoku_(board, x, y + 1)) {
                        return true;
                    }
                    board[x][y] = '.';
                }
            }
        }

        return false;


    }

    public boolean isTogether(int x, int y, char op, char[][] board) {
        //判断行
        for (int i = 0; i < board[x].length; i++) {
            if (i == y) {
                continue;
            }

            if (board[x][i] == op) {
                return false;
            }
        }
        //判断列
        for (int i = 0; i < board.length; i++) {
            if (i == x) {
                continue;
            }

            if (board[i][y] == op) {
                return false;
            }
        }

        //判断 3 * 3
        int tempX = x / 3 * 3;
        int tempY = y / 3 * 3;

        for (int i = tempX; i < tempX + 3; i++) {
            for (int j = tempY; j < tempY + 3; j++) {
                if (tempX == x && tempY == y) {
                    continue;
                }

                if (board[i][j] == op) {
                    return false;
                }
            }
        }

        return true;
    }


    @Test
    public void myTest() {
        //char[][] board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'},{'6', '.', '.', '1', '9', '5', '.', '.', '.'},{
        //'.', '9', '8', '.', '.', '.', '.', '6', '.'},{'8', '.', '.', '.', '6', '.', '.', '.', '3'},{
        //'4', '.', '.', '8', '.', '3', '.', '.', '1'},{'7', '.', '.', '.', '2', '.', '.', '.', '6'},{
        //'.', '6', '.', '.', '.', '.', '2', '8', '.'},{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
        //{'.','.','.','.','8','.','.','7','9'}};
        char[][] board = {{'5', '3', '.'},
                          {'6', '.', '.'},
                          {'.', '9', '8'}};
                          //{'8', '.', '.'},{'4', '.', '.'},{'7', '.', '.'},
                          //{'.', '6', '.'},{'.', '.', '.'},{'.', '.', '.'}};

        solveSudoku(board);
    }


}
